[LOJ10159]旅游规划

发表于 | 分类于 ， | | 阅读次数:


传送门

题解

树的直径不止一条，而题目要求我们把所有直径上的点给输出来。

数组名 数组作用
d1 i点到叶子节点的最长距离
d2 i点到叶子节点的次长距离
d3 i点向除子树外的最远距离

就拿样例来说，下面这个图应该很清楚了（红色的是树的直径）

显然，如果一个点满足d1+d2=树的直径或者d1+d3=树的直径，那么这个点肯定是树的直径上的点

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=200005;
int n;
int Nt[MAXN<<1],Head[MAXN<<1],to[MAXN<<1],tot;
int d1[MAXN],d2[MAXN],d3[MAXN],maxx;
 
inline int read(){
    char ch;ch=getchar();
    int x=0,f=1;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
 
void add(int x,int y){
    Nt[++tot]=Head[x];
    to[tot]=y;
    Head[x]=tot;
}
 
void dfs(int x,int fa){
    for(int i=Head[x];i;i=Nt[i]){
        int y=to[i];
        if(y==fa) continue;
        dfs(y,x);
        if(d1[y]+1>d1[x]){
            d2[x]=d1[x];
            d1[x]=d1[y]+1;
        }
        else if(d1[y]+1>d2[x]) d2[x]=d1[y]+1;
    }
    if(d1[x]+d2[x]>maxx) maxx=d1[x]+d2[x];
}
 
void dfs2(int x,int fa){
    for(int i=Head[x];i;i=Nt[i]){
        int y=to[i];
        if(y==fa) continue;
        if(d1[y]+1==d1[x]) d3[y]=max(d3[x],d2[x])+1;//如果子节点是d1更新的方向，那么就在父节点的d2,d3中取最大值
        else d3[y]=max(d3[x],d1[x])+1;
        dfs2(y,x);
    }
}
 
int main(){
    n=read();
    int x,y;
    for(int i=1;i<n;i++){
        x=read(),y=read();
        add(x,y);
        add(y,x);
    }
    dfs(0,0);
    dfs2(0,0);
    for(int i=0;i<n;++i) if(d3[i]+d1[i]==maxx||d1[i]+d2[i]==maxx) printf("%d\n",i);
    return 0;
}